import java.util.ArrayList;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class MergeSortedLists {

	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public ListNode mergeKLists(ArrayList<ListNode> lists) {
		int n = lists.size();
		if (n == 0)
			return null;
		ListNode res = new ListNode(0);
		ListNode cur = res;
		ListNode[] nodes = new ListNode[n];
		lists.toArray(nodes);
		while (true) {
			int max = Integer.MAX_VALUE;
			int idx = 0;
			for (int i = 0; i < n; ++i) {
				if (nodes[i] != null && nodes[i].val < max) {
					idx = i;
					max = nodes[i].val;
				}
			}
			if (max != Integer.MAX_VALUE) {
				ListNode newNode = new ListNode(max);
				cur.next = newNode;
				cur = cur.next;
				nodes[idx] = nodes[idx].next;
			} else {
				break;
			}
		}
		return res.next;
	}

	public static void main(String[] args) {

	}
}
